class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        for index, item in enumerate(inorder):
            if item == preorder[0]:
                mid_index = index
                break
        root = TreeNode(preorder[0])
        left_inorder = inorder[: mid_index]
        left_preorder = preorder[1 : 1 + len(left_inorder)]
        if mid_index == len(inorder) - 1:
            right_inorder = []
        else:
            right_inorder = inorder[mid_index + 1:]
            right_preorder = preorder[1 + len(left_inorder):]
        if len(left_inorder) > 0:
            root.left = self.buildTree(left_preorder, left_inorder)
        else:
            root.left = None
        if len(right_inorder) > 0:
            root.right = self.buildTree(right_preorder, right_inorder)
        else:
            root.right = None
        return root





